1. The Field of the Invention
The invention relates to methods, apparatus, and systems for resource arbitration. Specifically, the invention relates to methods, apparatus, and systems for reducing resource contention in multiprocessor systems.
2. The Relevant Art
The processing power of a computing system can be increased by employing multiple processors to share data processing tasks of the computing system. Although each processor may have its own dedicated resources, processors may also share system resources such as cache memory, main memory, communication buses, and peripheral devices. While completing their respective tasks, two or more processors will often concurrently request use of the same resource. For example, a processor may attempt to write data to a line of memory while another processor is concurrently attempting to read the same line of memory. The two processors must then arbitrate access to the line of memory.
Current arbitration methods allow a processor to reserve or secure a resource such as a line of memory. When a second requesting processor attempts to reserve a resource that is currently reserved by a first reservation holding processor, the second requesting processor is denied a reservation. The second requesting processor must make a subsequent reservation request.
In some cases, if a second requesting processor subsequently attempts to reserve a resource before the first reservation holding processor has released the resource, the first processor may lose its reservation and the second processor may be denied a reservation in order to maintain data integrity. Both processors must then arbitrate again for use of the resource. In some cases, multiple attempts to reserve the shared resource may be required in order to resolve the contention and allow each processor to access the shared resource and complete their tasks.
Another current method of arbitrating access to a resource involves calculating a random delay interval for each processor. Calculating a random delay interval reduces processor contention for a shared resource, but requires additional hardware or software complexity and produces an arbitrary distribution of delay intervals.
Still another current method of arbitrating access to a resource is to assign some processors higher priority for accessing a resource, or to lower the priority of some processors. Assigning different priority levels reduces contention, but often is biased against individual processors in the system, preventing all processors from completing their tasks as efficiently as possible.
What is needed is a method, apparatus, and system for reducing the contention for shared resources in multiprocessor systems. What is particularly needed is a method, apparatus, and system that delays a processors attempts to access a shared resource in order to minimize contention. The delay interval would preferably be unique to each processor, calculated with little computational overhead, and unbiased in providing access to resources. Such a method, apparatus, and system would provide efficient access to shared resources in an equitable manner.